1. Field of the Invention
The present invention relates to an image encoding device using a Markov model encoding system, and particularly to an image encoding device for improving compression efficiency without increasing a code table.
2. Description of the Related Art
The Markov model encoding is already known. An example of a Markov model encoding system described in, for example, pages 171 to 176 of "Compression of Image Information" (Ohm Co., Ltd.). In the Markov model encoding, an actual image is encoded on the assumption that the probability to determine which value would be taken or assumed as a pixel value of a given pixel, or a state thereof other than the pixel value or an index thereof, will depend on determining to which values a previous finite number of pixel values, states or indexes correspond. The pixel value, state and index will be described below on the condition that they are collectively referred to as "pixel values". The probability that a noted pixel to be encoded will be a given pixel value, will depends on patterns defined by values of m pixels preceding the noted pixel. If a conditional probability of the value of the noted pixel remains unchanged even if the preceding pixels are defined as m+1, then such an information source will be called "m-th order Markov source". The m pixels preceding the noted pixel will hereinafter be referred to as "reference pixels".
The value of the noted pixel will be defined as x(i) and the values of the m reference pixels will be defined as x(i-1), x(i-2), . . . , x(i-m). Assuming that a coupling probability is defined as P(x(i), x(i-1), x(i-2), . . . , x(i-m)) and a conditional probability is defined as P(x(i).vertline.x(i-1), x(i-2), . . . , x(i-m)), an entropy H of the m-th order Markov source is given by the following equation: ##EQU1##
This equation shows a theoretical compression limitation at the time that the preceding m symbols are given and x(i) is encoded. As described in page 174 in the "Compression of Image Information" (Ohm Co., Ltd.), the more the number of reference pixels increases, the more the theoretical compression limitation is reduced. Namely, compression efficiency is improved as the number of the reference pixels increases.
A specific Markov model encoding system is one intended to, for example, separate states from one another using reference pixels, prepare symbol or code tables, e.g. Huffman code tables every states and encode a pixel to be noted in this condition.
A process of generating state numbers from reference pixels will first be described with reference to FIG. 16. In FIG. 16, reference numerals 101, 102, 103, 104, 105 and 106 indicate an input image, an image memory, a reference pixel extracting circuit for extracting a reference pixel from the image memory 102, a value of the reference pixel, a state determining circuit for determining a state from the reference pixel, and a state number determined by the state determining circuit 105, respectively.
The input image 101 is temporarily inputted to the image memory 102. Pixels preceding a noted pixel to be now encoded have already been stored in the image memory 102. The reference pixel extracting circuit 103 extracts the reference pixel 104 corresponding to the noted pixel from the pixels stored in the image memory 102. The reference pixel extracting circuit 103 extracts two pixels of a located just on the left side of the noted pixel and b located just above the noted pixel as reference pixels as shown in FIG. 17, for example. The state determining circuit 105 determines the state number 106 based on the reference pixel 104.
After the determination of the state, encoding is effected on the noted pixel. For example, a code table for Huffman encoding is prepared for each state and the noted pixel is encoded based on the code table. Encoding is effected on the noted pixel in accordance with such a table as shown in FIG. 18, for example. In FIG. 18, the values of each reference pixel and the noted pixel have been described so as to be represented in 2 bits. Symbols or signs indicative of the respective states can be generated by examining the probability of generation of noted pixels assuming the states.
As has been described in "A study of Still Image Prediction Based on Learning Markov Model" (Proceedings of the 1995 IEICE General Conference, D-284, 1995), a system for predicting noted pixels every states after determination of the states is also known. According to this system, predicted values for the noted pixels are prepared with respect to the respective states. Difference encoding or the like is performed using the predicted values.
In either of the above systems, the total number of states becomes n.sup.m when the reference pixels provide n levels of halftone and the number of the reference pixels is m.
In the "A study of Still Image Prediction Based on Learning Markov Model" referred to above, the number of tones of the input image is 256. Namely, a 8-bit image is defined per pixel. When the number of reference pixels for the 8-bit image is 3, the total number of states becomes 256.times.256 .times.256=2.sup.24. Storing code tables or predicted values with respect to the respective states is at variance with the reality in terms of a hardware scale or software implementations. Therefore, the number of the reference pixels is set to the two pixels located just above the noted pixel and just on the left side thereof in the above-described "A study of Still Image Prediction Based on Learning Markov Model".
As described above, an improvement in the efficiency of the Markov model encoding needs to increase the number of the reference pixels. However, the prior art has a problem in that if the number of the reference pixels is increased when the tones of the input image are large in number, then the number of the states becomes great, so that hardware or software cannot be implemented or mounted.
However, even if the number of the tones of the input image is 256, there may be a case in which the number of types of pixel values in an actual input image is less than or equal to 256. For example, a two-value image assuming values of 0 and 255 alone and limited tonal images limited to 16 colors, 256 colors, etc. are known as examples of such a case. In this case, the encoding efficiency can be improved with an increase in the number of the reference pixels. However, since a selectable reference pixel range is one type alone in the conventional encoding system, the reference pixel could not be increased in number according to the input.